TOC-As-1

Question 1

$a.\mathbb{Z}\times \mathbb{Z}iscountable$.

Construct a counting procedure as below:

Each pair corresponds to a unique natural number. Therefore $\mathbb{Z}\times \mathbb{Z}$ is countalbe

$b.IfsetSiscountableandnisanaturalnumberconstant,then{S}^{n}iscountable$.

Case I

If $S$ is a finite set with $m$ element;

Then $|S^n|=m^n$ which is finite. Therefore $S^n$ is countable.

Case 2

If $S$ is a infinite and countable set; Then there must be a bijection between $S$ and $\mathbb{N}$.

And for 2 countable sets $A$ $B$, $A\times B$ is also a countable set.

For any element $(a,b)\in A\times B$ , we can write $a=f(i)$ and $b=g(j)$ for some $i,j\in \mathbb{N}$.

Therefore, $(a,b)$ corresponds to the pair $(f(i),g(j))$ , which in turn corresponds to the natural number pair $(i,j)$.

To establish a one-to-one correspondence, we can use a pairing function that maps each pair $(i,j)$ to a unique natural number k .

$$k=\frac{(i+j)(i+j+1)}{2}+j$$

Therefore, $A\times B$ is countable.

Since $S^n=S\times S\times \cdots \times S$ n times.

And $S\times S$ is countable.

Therefore $S^n$ is countable.

$c.|\{a|a\in \mathbb{R}\wedge 0<a<1\}|=\mathbb{R}$

Solution:

$Bijection|\{a|a\in \mathbb{R}\wedge 0<a<1\}|\to \mathbb{R}:tan(\pi x-\frac{\pi }{2})$

$d.\{a|a\in \mathbb{R}\wedge 0<a<10\}$ is uncountable.

Suppose a real number $a_i\in (0,10)$ denote as $a_i=a_{i,1}{a}_{i,2}\dots$. Then we build the table as below:

Index	$a_n$	Digits
0	$a_0$	$a_{0,0}{a}_{0,1}{a}_{0,2}\dots$
1	$a_1$	$a_{1,0}{a}_{1,1}{a}_{1,2}\dots$
2	$a_2$	$a_{2,0}{a}_{2,1}{a}_{2,2}\dots$
$⋮$	$⋮$	$⋮$

Next we define a real number $a_x=a_{x,0}{a}_{x,1}\dots$ such that $a_{x,i}=(a_{i,i}+2)mod10$. We can see a xis not in the list!

• $a_x$ and $a_0$ are different at digit 0.
• $a_x$ and $a_1$ are different at digit 1.
• $a_x$ and $a_2$ are different at digit 2.
• $a_x$ and $a_3$ are different at digit 3. $\dots$

Thus, $a_x$ is not counted and set of reals in (0, 10) is uncountable.

$\{f|f:\mathbb{N}\to \{0,1\}\}$ is uncountable

Assume that the set of functions from $\mathbb{N}$ to $\{0,1\}$ is countable.

Suppose all such functions can be listed as $f_1,f_2,f_3,\dots$.

Define a function $g$ such that $g(n)=1-f_n(n)$. This ensures that $g$ differs from each $f_i$ at least at position $i$.

Since $g$ is not equal to any $f_i$ in the list, this contradicts the assumption that we have listed all possible functions.

Therefore, the set of functions from $\mathbb{N}$ to $\{0,1\}$ is uncountable.

Question 2

Prove the followings.(1 pt for each)

a

$Foragivenalphabet\mathrm{\Sigma },thenumberofDF{A}^{{}^{\prime }}over\mathrm{\Sigma }iscountable$

b

Two sets are isomorphic if they are of the same cardinality. Prove that the number of DFA's (without specifying $\mathrm{\Sigma }$) is countable up to set isomorphism.

Question 3

Let $\mathrm{\Sigma }=\{a,b\}.$ Construct a DFA for each of the following languages. (10 pt for each)

a. $\{w|whasatleastonea\}$

Current State	$a$	$b$
$q_0$	$q_1$	$q_0$
$q_1$	$q_1$	$q_1$

b. $\{w|whasnomorethanthree{a}^{\prime }s\}$

Current State	$a$	$b$
$q_0$	$q_1$	$q_1$
$q_1$	$q_2$	$q_1$
$q_2$	$q_3$	$q_2$
$q_3$	$q_4$	$q_3$
$q_4$	$q_4$	$q_4$

c. $\{w|wdoesnothaveabasasubstring\}$

Current State	$a$	$b$
$q_0$	$q_1$	$q_2$
$q_1$	$q_1$	$q_3$
$q_2$	$q_1$	$q_2$
$q_3$	$q_3$	$q_3$

d. $\{w|wcontainsnorunsoflengthlessthanfor\}.$ A run in a string is a substring of length at least one and consisting entirely of the same symbol. For example, $abbbaab$ has four runs: $a,bbb,aa,b$.

Current State	$a$	$b$
$q_0$	$q_1$	$q_2$
$q_1$	$q_3$	$q_9$
$q_2$	$q_{10}$	$q_4$
$q_3$	$q_5$	$q_9$
$q_4$	$q_{10}$	$q_6$
$q_5$	$q_7$	$q_9$
$q_6$	$q_{10}$	$q_8$
$q_7$	$q_7$	$q_2$
$q_8$	$q_1$	$q_8$
$q_9$	$q_9$	$q_9$
$q_{10}$	$q_{10}$	$q_{10}$

Question 4

Let $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ be an arbitrary DFA. We construct a new DFA $M^{\prime }$ as $M^{\prime }=(Q,\mathrm{\Sigma },\delta ,q_0,Q\setminus F)$. We need to prove that $\overline{L(M)}=L(M^{\prime })$.

Note:

• $Q\setminus F$ is the set difference.
• $L(\bar{M})={\mathrm{\Sigma }}^{\ast }\setminus L(M)$ is the set complement.

---

The goal $L(\bar{M})=L(M^{\prime })$ is understood as set equality.
Thus, we need to prove $\mathrm{\forall }w\in {\mathrm{\Sigma }}^{\ast }$, $w\in L(\bar{M})⟺w\in L(M^{\prime })$.

($\Rightarrow$)
Assume $w\in L(\bar{M})$.
Then $w\notin L(M)$.
Thus, DFA $M$ rejects $w$.
In other words, DFA $M$ halts on a non-final state $q_x$ by consuming all symbols in $w$.
By the construction of $M^{\prime }$, $q_x$ is a final state of $M^{\prime }$.
Thus, $M^{\prime }$ accepts $w$, and $w\in L(M^{\prime })$.

---

($\Leftarrow$)
Assume $w\in L(M^{\prime })$.
DFA $M^{\prime }$ accepts $w$.
In other words, DFA $M^{\prime }$ halts on a final state $q_y$ by consuming all symbols in $w$.
By the construction of $M^{\prime }$, $q_y$ is a non-final state of $M$.
Thus, $M$ rejects $w$, so $w\notin L(M)$.
Thus, $w\in L(\bar{M})$. $L(\bar{M})=L(M^{\prime })$.